๋ฌธ์
Programmers - ๊ธธ ์ฐพ๊ธฐ ๊ฒ์
๐ Logic
public void insert(Node input) {
// root๊ฐ ์๋ค๋ฉด root ์ง์ , root๊ฐ ์๋ค๋ฉด, ์์ ๋
ธ๋ ํ์ํ์ฌ ์ ์ฅ
if (root == null) root = input;
else insert(input, root);
}
private void insert(Node input, Node root) {
// ๋ถ๋ชจ๋ณด๋ค x๊ฐ์ด ์์ ๊ฒฝ์ฐ์๋ left๋ฅผ ํ์, ๊ทธ๋ ์ง ์์ผ๋ฉด right ํ์
if (input.data.x < root.data.x) {
if (root.left == null) root.left = input;
else insert(input, root.left);
} else {
if (root.right == null) root.right = input;
else insert(input, root.right);
}
}
- ํธ๋ฆฌ๋ฅผ ์์ฑํ๋ ํจ์
- ๋
ธ๋์
x์ขํ๋ฅผ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ ๋๋ ์ค๋ฅธ์ชฝ ์์ ์ฌ๋ถ๊ฐ ๊ฒฐ์ ๋๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Loc {
int x;
int y;
int value;
public Loc(int x, int y, int value) {
this.x = x;
this.y = y;
this.value = value;
}
}
class Node {
Loc data;
Node left;
Node right;
public Node(Loc data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class Tree {
Node root;
int[] list;
int size;
int idx;
public Tree(int size) {
this.root = null;
this.size = size;
}
public void insert(Node input) {
// root๊ฐ ์๋ค๋ฉด root ์ง์ , root๊ฐ ์๋ค๋ฉด, ์์ ๋
ธ๋ ํ์ํ์ฌ ์ ์ฅ
if (root == null) root = input;
else insert(input, root);
}
private void insert(Node input, Node root) {
// ๋ถ๋ชจ๋ณด๋ค x๊ฐ์ด ์์ ๊ฒฝ์ฐ์๋ left๋ฅผ ํ์, ๊ทธ๋ ์ง ์์ผ๋ฉด right ํ์
if (input.data.x < root.data.x) {
if (root.left == null) root.left = input;
else insert(input, root.left);
} else {
if (root.right == null) root.right = input;
else insert(input, root.right);
}
}
public int[] preOrder() {
list = new int[size];
idx = 0;
preOrderTraversal(root);
return list;
}
private void preOrderTraversal(Node n) {
if (n == null) return;
list[idx++] = n.data.value;
preOrderTraversal(n.left);
preOrderTraversal(n.right);
}
public int[] postOrder() {
list = new int[size];
idx = 0;
postOrderTraversal(root);
return list;
}
private void postOrderTraversal(Node n) {
if (n == null) return;
postOrderTraversal(n.left);
postOrderTraversal(n.right);
list[idx++] = n.data.value;
}
}
class Solution {
public int[][] solution(int[][] nodeinfo) {
ArrayList<Loc> locs = new ArrayList<>();
int size = nodeinfo.length;
for (int i = 0; i < size; i++)
locs.add(new Loc(nodeinfo[i][0], nodeinfo[i][1], i + 1));
// x๊ฐ์ ์ค๋ฆ์ฐจ์, y๊ฐ์ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํ์ฌ BFS ํ์์ผ๋ก ๋ณํ
locs.sort(((o1, o2) -> {
if (o1.y == o2.y) return o1.x - o2.x;
return o2.y - o1.y;
}));
Tree t = new Tree(size);
for (Loc l : locs)
t.insert(new Node(l));
return new int[][] {t.preOrder(), t.postOrder()};
}
}
โ๏ธ Review
- ๊ณ ๋ฌธํด์๊ฐ์ BFS ํ์์ผ๋ก ์ ๋ ฅ๋ฐ์ ์ด๋ฅผ preorder, postorder๋ก ์ถ๋ ฅํ๋ ๊ณผ์ ๊ฐ ์๊ฐ๋ ์์ด๋์ด๋ ์ฝ๊ฒ ์ก์ ์ ์์๋ค.
-
x๊ฐ ์ขํ์ ๋ฐ๋ฅธ ์ผ์ชฝ, ์ค๋ฅธ์ชฝ ์์ ์ฌ๋ถ์ ๋ํ ๊ณ ๋ ค๋ฅผ ํตํด ํธ๋ฆฌ๋ฅผ ์์ฑํด์ผ ํ๋ ์๊ฐ์ด ํค ํฌ์ธํธ์์ง ์์๊น ..
insert()๋ฅผ ์ค๋ฒ๋ก๋ฉํ๋ ๋ฐฉ์์ ์ฌ์ฉํด๋ณด์๋ค!